package com.xjj.dbfs;

import java.util.*;

public class M0017LetterCombinationsOfAPhoneNumber {

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.equals("")) {
            return new ArrayList<>();
        }
        Map<Character, List<String>> map = new HashMap<>();
        map.put('2', Arrays.asList("a", "b", "c"));
        map.put('3', Arrays.asList("d", "e", "f"));
        map.put('4', Arrays.asList("g", "h", "i"));
        map.put('5', Arrays.asList("j", "k", "l"));
        map.put('6', Arrays.asList("m", "n", "o"));
        map.put('7', Arrays.asList("p", "q", "r", "s"));
        map.put('8', Arrays.asList("t", "u", "v"));
        map.put('9', Arrays.asList("w", "x", "y", "z"));
        Queue<String> queue = new LinkedList<>();
        queue.offer("");
        for (int i = 0; i < digits.length(); i++) {
            int index = queue.size();
            for(int j = 0; j < index; j++) {
                String before = queue.poll();
                for (String s : map.get(digits.charAt(i))) {
                    queue.offer(before + s);
                }
            }
        }
        return new ArrayList<>(queue);
    }
}
